package leetcode.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import datastructure.binarytree.TreeNode;

public class LeetCode297 {
     // Encodes a tree to a single string.
     public String serialize(TreeNode root) {
         if (root == null) {
             return null;
         }
         StringBuilder sb = new StringBuilder();
         preOrder(root, sb);
         return sb.substring(1).toString();
    }
    void preOrder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(",null");
            return;
        }
        sb.append("," + root.val);
        preOrder(root.left, sb);
        preOrder(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        List<String> list = new LinkedList<>(Arrays.asList(data.split(",")));
        if (list == null || list.isEmpty()) {
            return null;
        }
        return preOrder(list);
    }
    TreeNode preOrder(List<String> list) {
        String first = list.remove(0);
        if ("null".equals(first)) {
            return null;
        }
        TreeNode n = new TreeNode(Integer.valueOf(first));
        n.left = preOrder(list);
        n.right = preOrder(list);
        return n;
    }
}
